package cn.fxzhang.leetcode.no01;

/**
 * 153. 寻找旋转排序数组中的最小值
 * 提示：
 * n == nums.length
 * 1 <= n <= 5000
 * -5000 <= nums[i] <= 5000
 * nums 中的所有整数 互不相同
 * 输入：nums = [3,4,5,1,2]
 * 输出：1
 * 类型：数组/二分查找
 * 题解：根据有序性，可以用枚举或者二分
 * 时间复杂度：O(lg(N))
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 37.9 MB, 52.83%
 *
 * 【中等】通过次数116,961提交次数267,848
 * @author 张晓帆
 * @date 2021/4/8
 */
public class P0153_Find_Minimum_In_Rotated_Sorted_Array {

    public int findMin(int[] nums) {
        return binaryFindMin(nums, 0, nums.length-1);
    }

    private int binaryFindMin(int[] nums, int l, int r) {
        if (nums[l] <= nums[r]){
            return nums[l];
        }
        int mid = (l+r) >> 1;
        return nums[mid]>nums[r]? binaryFindMin(nums, mid+1, r): binaryFindMin(nums, l, mid);
    }
}
